Exact sampling for intractable probability distributions via a Bernoulli factory

摘要

Many applications in the field of statistics require Markov chain Monte Carlomethods. Determining appropriate starting values and run lengths can be bothanalytically and empirically challenging. A desire to overcome these problemshas led to the development of exact, or perfect, sampling algorithms whichconvert a Markov chain into an algorithm that produces i.i.d. samples from thestationary distribution. Unfortunately, very few of these algorithms have beendeveloped for the distributions that arise in statistical applications, whichtypically have uncountable support. Here we study an exact sampling algorithmusing a geometrically ergodic Markov chain on a general state space. Our workprovides a significant reduction to the number of input draws necessary for theBernoulli factory, which enables exact sampling via a rejection samplingapproach. We illustrate the algorithm on a univariate Metropolis-Hastingssampler and a bivariate Gibbs sampler, which provide a proof of concept andinsight into hyper-parameter selection. Finally, we illustrate the algorithm ona Bayesian version of the one-way random effects model with data from a styreneexposure study.